Lý thuyết hình thức Chuỗi_trống

Xét về hình thức, chuỗi là một dãy ký tự (như chữ cái, chữ số hoặc khoảng trắng) có giới hạn, có thứ tự. Chuỗi trống là trường hợp đặc biệt khi dãy ký tự có độ dài bằng 0, như vậy, chuỗi trống không chứa bất kỳ ký tự nào.Bởi vì hai chuỗi được xác định là khác nhau nếu chúng có độ dài khác nhau hoặc có dãy ký tự khác nhau, nên chỉ tồn tại duy nhất một chuỗi trống.In formal treatments,[1] chuỗi trống được ký hiệu là ε hoặc đôi khi là Λ hoặc λ.

Không nên nhầm lẫn chuỗi trống với ngôn ngữ trống (empty language) ∅, là một ngôn ngữ hình thức (tập hợp các chuỗi) không chứa bất kỳ chuỗi nào, kể cả chuỗi trống.

Chuỗi trống có các tính chất sau:

  • |ε| = 0. Chiều dài chuỗi bằng 0.
  • ε ⋅ s = s ⋅ ε = s. Chuỗi trống là phần tử đơn vị của phép nối chuỗi. Tập hợp tất cả chuỗi tạo thành một monoid tự do đối với ⋅ và ε.
  • εR = ε. Nghịch đảo của chuỗi trống cũng là một chuỗi trống.
  • Chuỗi trống đứng trước mọi chuỗi còn lại theo thứ tự từ điển, bởi vì nó có độ dài ngắn nhất.[2]